import java.util.Date;
	import java.util.* ;
public class HeapDist {
	private Node[] heapDist;
	private int maxSize;
	private int currentSize;
	public HeapDist(int max){
		maxSize=max;
		currentSize=0;
		heapDist=new Node[maxSize];
	}
	public boolean isEmpty(){
		return currentSize==0;
	}

	public boolean insert(String clientName,String clock,int distance,int numOfPizza,Object next){
		if(currentSize==maxSize)
	        return false;
	     Node newNode = new Node(clientName,clock,distance,numOfPizza,next,currentSize);
	     heapDist[currentSize]=	newNode;
	     trickleUp(currentSize++);
	     return true;
	     }  // end insert()
		
	public void trickleUp(int index)
	{
	int parent = (index-1) / 2;
	Node bottom = heapDist[index];

	while( index > 0 &&
			heapDist[parent].getDistance() < bottom.getDistance() )
	   {
		heapDist[index] = heapDist[parent];  // move it down
	   index = parent;
	   parent = (parent-1) / 2;
	   }  // end while
	heapDist[index] = bottom;
	
	}  // end trickleUp()

	public Node removeDist()           // delete item with max key
	{                           // (assumes non-empty list)
	Node rootDist = heapDist[0];
	heapDist[0] = heapDist[--currentSize];
	trickleDown(0);
	return rootDist;
	}  // end remove()

	   public void trickleDown(int index)
	      {
	      int largerChild;
	      Node top = heapDist[index];       // save root
	      while(index < currentSize/2)       // while node has at
	         {                               //    least one child,
	         int leftChild = 2*index+1;
	         int rightChild = leftChild+1;
	                                         // find larger child
	         if(rightChild < currentSize &&  // (rightChild exists?)
	        		 heapDist[leftChild].getDistance() <
	        		 heapDist[rightChild].getDistance())
	            largerChild = rightChild;
	         else
	            largerChild = leftChild;
	                                         // top >= largerChild?
	         if( top.getDistance() >= heapDist[largerChild].getDistance() )
	                                         // shift child up
	        	 heapDist[index] = heapDist[largerChild];
	         index = largerChild;            // go down
	         }  // end while
	      heapDist[index] = top;            // root to index
	      }  // end trickleDown()
	   
	   
	public static boolean firstIsBigger(String s1,String s2) {
		StringTokenizer first = new StringTokenizer(s1,":" + " ");
		StringTokenizer sec = new StringTokenizer(s2,":" + " ");
		int num1=Integer.valueOf(first.nextToken()).intValue()*100 + Integer.valueOf(first.nextToken()).intValue();
		int num2=Integer.valueOf(sec.nextToken()).intValue()*100 + Integer.valueOf(sec.nextToken()).intValue();
		return num1>num2;
	}
	}

